import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by JiaJia on 2019/8/10 0010.
 */
public class Beike02 {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while (scanner.hasNext()){
            int n=scanner.nextInt();
            int[] arr=new int[n];
            for (int i = 0; i <n ; i++) {
                arr[i]=scanner.nextInt();
            }
            System.out.println(solution(arr));
        }
        scanner.close();
    }
    private static int solution(int[] nums){
       /*
        int MAX=0;
        int[] res=new int[50001];
        for (int i = 0; i <nums.length ; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    res[i] = Math.max(res[i], res[j] + 1);
                    MAX = Math.max(MAX, res[i]);
                }
            }
        }
        return MAX+1;*/
       /* if (nums.length==0){
            return 0;
        }
        int[] dp=new int[nums.length];
        dp[0]=1;
        int max=1;
        for (int i = 0; i <dp.length ; i++) {
            int maxValue=0;
            for (int j = 0; j <i ; j++) {
                if (nums[i]>nums[j]){
                    maxValue=Math.max(maxValue,dp[j]);
                }
            }
            dp[i]=maxValue+1;
            max=Math.max(max,dp[i]);
        }
        return max;*/
        int[] dp=new int[nums.length];
        int len=0;
        for (int num:nums) {
            int i= Arrays.binarySearch(dp,0,len,num);
            if (i<0){
                i=-(i+1);
            }
            dp[i]=num;
            if (i==len){
                len++;
            }
        }
        return len;
    }
}